#include "stdafx.h"
#include "t04_rand_qsort_find.h"

#include <stdlib.h>
#include <memory.h>
#include <time.h>

typedef int(*COMPAR)(const void*, const void*);
#define VEC(p, i, type_size) ((void*)(((char*)(p))+(type_size)*(i)))
#define SET_TEST_FLAG 0

typedef enum {    NO_SAME,    HAVE_SAME}SET_T;
typedef enum {    RET_OK,    RET_NG}RET_T;

typedef unsigned long u_long;

void free_data(void **p, long *cnt){
    if(NULL != *p) {
        free(*p);
        *p = NULL;
    }
    if(NULL != cnt) {
		*cnt = 0;
    }
    return;
}

int cmp_key_n(const void *l, const void *r, const int key_count)
{
    long *pl = (long*)l;
    long *pr = (long*)r;
    int loop_key = 0;
    //
    for(loop_key = 0; loop_key < key_count; ++loop_key) {
        if(pl[loop_key] != pr[loop_key]) {
            return pl[loop_key] - pr[loop_key];
        }
    }
    return 0;
}

int cmp_key_1(const void *l, const void *r)
{
    return *((long*)l) - *((long*)r);
}

int cmp_key_2(const void *l, const void *r)
{
    if(*((long*)l) != *((long*)r)) {
        return *((long*)l) - *((long*)r);
    }
    else {
        return ((long*)l)[1] - ((long*)r)[1];
    }
}

int cmp_key_3(const void *l, const void *r) {return cmp_key_n(l, r, 3)       ;}
int cmp_key_4(const void *l, const void *r) {return cmp_key_n(l, r, 4)       ;}
int cmp_key_5(const void *l, const void *r) {return cmp_key_n(l, r, 5)       ;}
int cmp_key_6(const void *l, const void *r) {return cmp_key_n(l, r, 6)       ;}
int cmp_key_7(const void *l, const void *r) {return cmp_key_n(l, r, 7)       ;}
int cmp_key_8(const void *l, const void *r) {return cmp_key_n(l, r, 8)       ;}

//void**
int cmp_pkey_n(const void *l, const void *r, const int key_count)
{
    long *pl = *(long**)l;
    long *pr = *(long**)r;
    int loop_key = 0;
    //
    for(loop_key = 0; loop_key < key_count; ++loop_key) {
        if(pl[loop_key] != pr[loop_key]) {
            return pl[loop_key] - pr[loop_key];
        }
    }
    return 0;
}

int cmp_pkey_1(const void *l, const void *r)
{
    return **((long**)l) - **((long**)r);
}

int cmp_pkey_2(const void *l, const void *r)
{
    if(**((long**)l) != **((long**)r)) {
        return **((long**)l) - **((long**)r);
    }
    else {
        return (*(long**)l)[1] - (*(long**)r)[1];
    }
}

int cmp_pkey_3(const void *l, const void *r) {return cmp_pkey_n(l, r, 3)          ;}
int cmp_pkey_4(const void *l, const void *r) {return cmp_pkey_n(l, r, 4)          ;}
int cmp_pkey_5(const void *l, const void *r) {return cmp_pkey_n(l, r, 5)          ;}
int cmp_pkey_6(const void *l, const void *r) {return cmp_pkey_n(l, r, 6)          ;}
int cmp_pkey_7(const void *l, const void *r) {return cmp_pkey_n(l, r, 7)          ;}
int cmp_pkey_8(const void *l, const void *r) {return cmp_pkey_n(l, r, 8)          ;}

u_long set_count_diff(void *set, u_long cnt, size_t type_size, COMPAR f)
{
    u_long item_cnt = 0;
    u_long i = 0;
    //
    if(cnt <= 1) {
        return cnt;
    }
    item_cnt = 1;
    for(i = 1; i < cnt; ++i) {
        if(0 != f(VEC(set, i-1, type_size), VEC(set, i, type_size))) {
            ++item_cnt;
        }
    }
    return item_cnt;
}

int set_copy_diff(void *from, u_long from_cnt, size_t type_size, COMPAR f,
                        void *to, u_long to_cnt)
{
    u_long item_cnt = 0;
    u_long i = 0;
    //
    if(from_cnt == 0) {
        return RET_OK;
    }
    if(from_cnt == 1) {
        memcpy(to, from, type_size);
        return RET_OK;
    }
    memcpy(to, from, type_size);
    for(i = 1; i < from_cnt; ++i) {
        if(0 != f(VEC(from, i-1, type_size), VEC(from, i, type_size))) {
            ++item_cnt;
            if(item_cnt >= to_cnt) {
                printf("OVERFLOW ERROR.\n");
                return RET_NG;
            }
            else {
                memcpy(VEC(to, item_cnt, type_size), VEC(from, i, type_size), type_size);
            }
        }
    }
    return RET_OK;
}

SET_T set_type_check(void *set, u_long cnt, size_t type_size, COMPAR f)
{
    u_long diff_cnt = 0;
    //
    diff_cnt = set_count_diff(set, cnt, type_size, f);
    if(cnt == diff_cnt) {
        return NO_SAME;
    }
    else {
        return HAVE_SAME;
    }
}

bool set_is_sorted(void *set, u_long cnt, size_t type_size, COMPAR f)
{
    u_long i = 0;
    //
    if(cnt <= 1) {
        return true;
    }
    for(i = 1; i < cnt; ++i) {
        if(f(VEC(set, i-1, type_size), VEC(set, i, type_size)) > 0) {
            return false;
        }
    }
    return true;
}

int set_build(void **set, u_long *cnt, size_t type_size, COMPAR f, SET_T flag)
{
    u_long item_cnt = 0;
    char *p = NULL;
    //
    qsort(*set, *cnt, type_size, f);
    //
    if(HAVE_SAME == flag) {
        return RET_OK;
    }
    else {
        item_cnt = set_count_diff(*set, *cnt, type_size, f);
        if(item_cnt > *cnt) {
            printf("set_count_diff ERROR.\n");
            return RET_NG;
        }
        if(item_cnt == *cnt) {
            return RET_OK;
        }
        p = (char*)malloc(type_size * item_cnt);
        if(NULL == p) {
            printf("malloc ERROR.\n");
            return RET_NG;
        }
        memset(p,  0x00, type_size * item_cnt);

        if(RET_OK != set_copy_diff(*set, *cnt, type_size, f, (void*)p, item_cnt)) {
            printf("set_copy_diff ERROR.\n");
            return RET_NG;
        }
        free_data(set, (long*)cnt);
        *set = p;
        *cnt = item_cnt;
        return RET_OK;
    }
}

void *set_find(void *set, u_long cnt, size_t type_size, COMPAR f,
                void *key, u_long *item_cnt)
{
    u_long i = 0;
    u_long cnt_temp = 0;
    void *p = NULL;
    //
#if SET_TEST_FLAG
    if(false == set_is_sorted(set, cnt, type_size, f)) {
        printf("set must sort before set_find.\n");
        return NULL;
    }
#endif
    //
    p = bsearch(key, set, cnt, type_size, f);
    if(NULL == p) {
        if(NULL != item_cnt) {
            *item_cnt = 0;
        }
        return p;
    }
    else {
        if(NULL == item_cnt) {
            return p;
        }
        i = ((size_t)p - (size_t)set) / type_size;
        for(; i > 0; --i) {
            if(0 == f(VEC(set, i-1, type_size), VEC(set, i, type_size))) {
                continue;
            }
            else {
                break;
            }
        }
        p = VEC(set, i, type_size);
        cnt_temp = 1;
        for(++i; i < cnt; ++i) {
            if(0 == f(VEC(set, i-1, type_size), VEC(set, i, type_size))) {
                ++cnt_temp;
            }
            else {
                break;
            }
        }
        *item_cnt = cnt_temp;
    }
    return p;
}

int set_minus(void *a, u_long a_cnt, size_t type_size, COMPAR f,
                 void *b, u_long b_cnt,
                 void **c, u_long *c_cnt)
{
    u_long item_cnt = 0;
    u_long i = 0;
    void *p = NULL;
    //
    if(NULL != *c) {
        free_data(c, (long*)c_cnt);
    }
#if SET_TEST_FLAG
    if(false == set_is_sorted(b, b_cnt, type_size, f)) {
        printf("set must sort before set_minus.\n");
        return RET_NG;
    }
#endif
    for(i = 0, item_cnt = 0; i < a_cnt; ++i) {
        p = set_find(b, b_cnt, type_size, f, VEC(a, i, type_size), NULL);
        if(NULL == p) {
            ++item_cnt;
        }
    }
    if(item_cnt > 0) {
        *c = malloc(type_size * item_cnt);
        if(NULL == *c) {
            printf("malloc ERROR.\n");
            return RET_NG;
        }
        *c_cnt = item_cnt;
        for(i = 0, item_cnt = 0; i < a_cnt; ++i) {
            p = set_find(b, b_cnt, type_size, f, VEC(a, i, type_size), NULL);
            if(NULL == p) {
                memcpy(VEC(*c, item_cnt, type_size), VEC(a, i, type_size), type_size);
                ++item_cnt;
            }
        }
    }
    else {
        *c = NULL;
        *c_cnt = 0;
    }
    return RET_OK;
}

int set_intersection(void *a, u_long a_cnt, size_t type_size, COMPAR f,
                 void *b, u_long b_cnt,
                 void **c, u_long *c_cnt)
{
    u_long item_cnt = 0;
    u_long i = 0;
    void *p = NULL;
    //
    if(NULL != *c) {
        free_data(c, (long*)c_cnt);
    }
#if SET_TEST_FLAG
    if(false == set_is_sorted(b, b_cnt, type_size, f)) {
        printf("set b must sort before set_intersection.\n");
        return RET_NG;
    }
#endif
    for(i = 0, item_cnt = 0; i < a_cnt; ++i) {
        p = set_find(b, b_cnt, type_size, f, VEC(a, i, type_size), NULL);
        if(NULL != p) {
            ++item_cnt;
        }
    }
    if(item_cnt > 0) {
        *c = malloc(type_size * item_cnt);
        if(NULL == *c) {
            printf("malloc ERROR.\n");
            return RET_NG;
        }
        *c_cnt = item_cnt;
        for(i = 0, item_cnt = 0; i < a_cnt; ++i) {
            p = set_find(b, b_cnt, type_size, f, VEC(a, i, type_size), NULL);
            if(NULL != p) {
                memcpy(VEC(*c, item_cnt, type_size), VEC(a, i, type_size), type_size);
                ++item_cnt;
            }
        }
    }
    else {
        *c = NULL;
        *c_cnt = 0;
    }
    return RET_OK;
}

struct MyStruct{
	union{
		u_long key[2];
		struct{
			int x,y;
		};
	};
	int z;
};
void rand_MyStruct(MyStruct *p, int cnt){
	if(!p)return;
	if(!cnt)return;
	srand((int)time(0));
	for(int i = 0; i < cnt; ++i){
		p[i].x = rand();
		p[i].y = rand();
		p[i].z = rand();
	}
}
void print_MyStruct(MyStruct *p, int cnt, char *msg){
	if(!p)return;
	if(!cnt)return;
	printf("%s\n", msg);
	for(int i = 0; i < cnt; ++i){
		printf("%d\t:%d %d %d\n", i, p[i].x, p[i].y, p[i].z);
	}
}
void print_MyStruct(MyStruct **p, int cnt, char *msg){
	if(!p)return;
	if(!cnt)return;
	printf("%s\n", msg);
	for(int i = 0; i < cnt; ++i){
		printf("%d\t:%d %d %d\n", i, p[i]->x, p[i]->y, p[i]->z);
	}
}
void t04_rand_qsort_find(void){
	u_long cnt = 10;
	MyStruct *p = (MyStruct *)malloc(sizeof(MyStruct) * cnt);
	if(!p)printf("malloc ERROR.\n");
	//
	rand_MyStruct(p, cnt);
	print_MyStruct(p, cnt, "rand");
	//
    if(RET_OK != set_build((void**)&p, &cnt,
                            sizeof(MyStruct), cmp_key_2, NO_SAME)) {
        printf("set_build ERROR.\n");
    }
	print_MyStruct(p, cnt, "set_build");
	//
	MyStruct **pp = (MyStruct **)malloc(sizeof(MyStruct*) * cnt);
	if(!pp)printf("malloc ERROR.\n");
	rand_MyStruct(p, cnt);
	for(u_long i = 0; i < cnt; ++i){
		pp[i] = &(p[i]);
	}
	print_MyStruct(pp, cnt, "rand2");
    if(RET_OK != set_build((void**)&pp, &cnt,
                            sizeof(MyStruct*), cmp_pkey_2, NO_SAME)) {
        printf("set_build ERROR.\n");
    }
	print_MyStruct(pp, cnt, "set_build_p");
	//
    free_data((void**)&p, (long*)&cnt);
    free_data((void**)&pp, (long*)&cnt);
}
